package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 图的遍历
 */
public class Traversal {

    /**
     邻接表节点数据类型内部类
     */
    private static class Node {
        int num;  //节点编号
        int data;
        Edge edge;  //边链表的头结点指针域

        public Node(int num) {
            this.num = num;
        }

        public Edge edge(int target) {
            this.edge = new Edge(target);
            return this.edge;
        }

    }

    /**
     邻接表边数据类型内部类
     */
    private static class Edge {
        int target;  //边的另一端节点编号
        Edge next;  //后继指针域

        public Edge(int target) {
            this.target = target;
        }

        public Edge next(int target) {
            this.next = new Edge(target);
            return this.next;
        }

    }

    /**
     图的深度优先遍历
     graph为图的邻接表
     */
    public List<Integer> deepFirstTraversal(Node[] graph) {

        if(graph.length == 0) {
            return null;
        }

        //结果序列
        List<Integer> result = new ArrayList<>();
        //记录节点被访问情况的数组
        boolean[] visited = new boolean[graph.length];

        //执行图的深度优先遍历
        deepFirstTraversalInner(graph, 0, visited, result);
        return result;

    }

    /**
     图的深度优先遍历过程方法
     graph为图的邻接表
     num为被遍历节点的编号
     visited为记录节点被访问情况的数组
     result为结果序列
     */
    private void deepFirstTraversalInner(
            Node[] graph, int num,
            boolean[] visited, List<Integer> result) {
        if(visited[num]) {
            return;
        }

        result.add(graph[num].data);
        visited[num] = true;

        //对图的邻居节点执行深度优先遍历
        Edge edge = graph[num].edge;
        while(edge != null) {
            deepFirstTraversalInner(graph, edge.target, visited, result);
            edge = edge.next;
        }

    }

    /**
     图的广度优先遍历
     graph为图的邻接表
     */
    public List<Integer> breadthFirstTraversal(Node[] graph) {

        if(graph.length == 0) {
            return null;
        }

        //结果序列
        List<Integer> result = new ArrayList<>();

        //记录节点被访问情况的数组
        boolean[] visited = new boolean[graph.length];

        //广度优先遍历的辅助队列
        Queue<Node> queue = new LinkedList<>();

        //图中编号最小的节点初始入队列
        queue.offer(graph[0]);
        visited[0] = true;
        //循环条件为队列非空
        while(!queue.isEmpty()) {
            //出队列一个节点
            Node node = queue.poll();
            result.add(node.data);
            /*
             将当前节点的邻居节点入队列，
             并标记为已访问
             */
            Edge edge = node.edge;
            while(edge != null) {
                if(!visited[edge.target]) {
                    queue.offer(graph[edge.target]);
                    visited[edge.target] = true;
                }
                edge = edge.next;
            }
        }
        return result;

    }

    public static void main(String[] args) {
        Node[] graph = new Node[6];
        for(int i = 0; i < graph.length; i++) {
            graph[i] = new Node(i);
            graph[i].data=i+1;
        }
        graph[0].edge(1).next(2);
        graph[1].edge(0).next(3).next(4);
        graph[2].edge(0).next(5);
        graph[3].edge(1).next(4);
        graph[4].edge(1).next(3).next(5);
        graph[5].edge(2).next(4);

        Traversal t = new Traversal();

        System.out.println("----------图的深度优先遍历----------");
        List<Integer> result1 = t.deepFirstTraversal(graph);
        System.out.println(result1);
        System.out.println("----------图的广度优先遍历----------");
        List<Integer> result2 = t.breadthFirstTraversal(graph);
        System.out.println(result2);

    }

}
